package lcr;

public class Test0093 {
    public static void main(String[] args) {
        new Solution0093_1().lenLongestFibSubseq(new int[]{1,2,3,4,5,6,7,8});
    }
}

class Solution0093_1 {
    public int lenLongestFibSubseq(int[] arr) {
        int length = arr.length;
        int[][] dp = new int[length][length];

        int ans=0;
        for (int i = 2; i < length; i++) {
            int num = arr[i];
            int l=0,r=i-1;

            while (l<r){
                if (num<arr[l]+arr[r]) r--;
                else if (num>arr[l]+arr[r]) l++;
                else{
                    if (dp[l][r]==0) dp[r][i]=Math.max(dp[r][i],3);
                    else dp[r][i]=Math.max(dp[l][r]+1,dp[r][i]);
                    ans=Math.max(ans,dp[r][i]);
                    l++;
                    r--;

                }

            }
        }
        return ans;
    }
}
